1168A - Increasing by Modulo - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N=300010;

int n,m;
int w[N];

bool check(int mid){
    vector<int> t(n+1);
    for(int i=0;i<n;++i) t[i]=w[i];
    t[n]=m;
    for(int i=n-1;i>=0;--i){
        if(t[i+1]>=t[i]){
            if(t[i]+mid>=m) t[i]=t[i+1];
            else t[i]=min(t[i]+mid,t[i+1]);
        }
        else{
            if(t[i]+mid>=m) t[i]=min(t[i+1],(t[i]+mid)%m);
            else return false;
        }
        // cout<<t[i]<<" ";
    }
    // cout<<endl;
    // for(int i=0;i<n;++i){
    //     if(w[i]>w[i+1]) return false;
    // }
    return true;
}

int main(){
#ifdef DEBUG
    freopen("test.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n>>m;
    for(int i=0;i<n;++i) cin>>w[i];

    int l=0,r=m;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l;
    // cout<<check(0)<<endl;
}